package Lagou.Queue;

/**
 * 例 1：二叉树的层次遍历（两种方法）leetcode-T102
 * https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
 *
 * 从上到下按层打印二叉树，同一层结点按从左到右的顺序打印，每一层打印到一行。
 * */

import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;



class Queue01 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
     }
 }
    //方案一
    public List<List<Integer>> levelOrder(TreeNode root) {
        //生成FIFO队列
        Queue<TreeNode> Q = new LinkedList<>();
        //如果节点不为空，则加入队列
        if (root != null) Q.offer(root);

        //用于保存层次遍历的结果
        List<List<Integer>> ans = new LinkedList<>();
        //开始利用FIFO队列进行层次遍历
        while (Q.size() > 0) {
            //取出当前层里面元素的个数
            final int qSize = Q.size();
            //当前节点放入temp链表中
            List<Integer> temp = new LinkedList<>();
            //遍历当前层的每个节点
            for (int i = 0; i < qSize; i++) {
                //当前层前面的结点先出队
                TreeNode cur = Q.poll();
                //把结果存放当于当前层中
                temp.add(cur.val);
                //把下一层的结点入队，注意入队时需要非空才可以入队。
                if (cur.left != null) Q.offer(cur.left);
                if (cur.right != null) Q.offer(cur.right);
            }
            ans.add(temp);
        }

        return ans;
    }

    //方案二
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        //初始化当前节点
        List<TreeNode> curLevel = new ArrayList<>();

        //root不为空时加入
        if (root != null) curLevel.add(root);
        while (curLevel.size() > 0) {
            //准备存放下一层节点
            List<TreeNode> nextLevel = new ArrayList<>();
            //用来存放当前层的结果
            List<Integer> curResult = new ArrayList<>();

            //遍历当前层的每个节点
            for (TreeNode cur: curLevel) {
                // 把当前层的值存放到当前结果里面
                curResult.add(cur.val);
                //生成下一层
                if (cur.left != null) nextLevel.add(cur.left);
                if (cur.right != null) nextLevel.add(cur.right);
            }
            // 注意这里的更迭!滚动前进
            curLevel = nextLevel;
            // 把当前层的值放到结果里面
            ans.add(curResult);
        }
        return ans;
    }
}
